package pers.lls.hds.tree;

import java.util.Stack;

/**
 * 二叉树迭代实现
 */
public class BSTIterative {

    private Node root;

    BSTIterative() {
        root = null;
    }

    public static void main(String[] args) {
        BSTIterative tree = new BSTIterative();
        tree.add(5);
        tree.add(8);
        tree.add(4);
        tree.add(9);
        tree.add(7);
        tree.add(3);
        tree.add(2);
        tree.add(10);
        System.out.println();
        Node n9 = tree.find(9);
        System.out.println();
        tree.remove(8);
        System.out.println();

    }


    public void add(int data) {
        Node parent;
        Node temp = this.root;
        while (temp != null) {
            if (data < temp.data) {
                parent = temp;
                temp = parent.left;
                if (temp == null){
                    Node newNode = new Node(data);
                    parent.left = newNode;
                    return;
                }
            } else if (data > temp.data) {
                parent = temp;
                temp = parent.right;
                if (temp == null){
                    Node newNode = new Node(data);
                    parent.right = newNode;
                    return;
                }
            } else {
                return;
            }
        }
        Node newNode = new Node(data);
        this.root = newNode;
    }

    public Node find(int data) {
        Node temp = this.root;
        while (temp != null) {
            if (data < temp.data) {
                temp = temp.left;
            } else if (data > temp.data) {
                temp = temp.right;
            } else {
                return temp;
            }
        }
        return null;
    }

    public void remove(int data) {
        Node parent;
        Node temp = this.root;
        while (temp != null) {
            if (data < temp.data) {
                parent = temp;
                temp = parent.left;
                if (temp.data == data){
                    move(parent, temp);
                    return;
                }
            } else if (data > temp.data){
                parent = temp;
                temp = parent.right;
                if (temp.data == data){
                    move(parent, temp);
                    return;
                }
            }else {
                break;
            }
        }

    }

    private void move(Node parent, Node temp){
        if (temp.right == null && temp.left == null) {
            parent.left = null;
        } else if (temp.right == null) {
            parent.left = temp.left;
        } else if (temp.left == null) {
            parent.left = temp.right;
        } else {
            if (temp.right.left == null) {
                temp.data = temp.right.data;
                temp.right = temp.right.right;
            } else {
                Node parent2 = temp.right;
                Node child = temp.right.left;
                while (child.left != null) {
                    parent2 = child;
                    child = parent2.left;
                }
                temp.data = child.data;
                parent2.left = child.right;
            }
        }
    }

    public void inorder() {
        if (this.root == null) {
            return;
        }
        Stack<Node> st = new Stack<>();
        Node cur = this.root;
        while (cur != null || !st.empty()) {
            while (cur != null) {
                st.push(cur);
                cur = cur.left;
            }
            cur = st.pop();
            cur = cur.right;
        }
    }

    public void postorder() {
        if (this.root == null) {
            return;
        }
        Stack<Node> st = new Stack<>();
        Node cur = this.root, temp2;
        while (cur != null || !st.empty()) {
            if (cur != null) {
                st.push(cur);
                cur = cur.left;
            } else {
                temp2 = st.peek();
                if (temp2.right != null) {
                    cur = temp2.right;
                } else {
                    st.pop();
                    while (!st.empty() && st.peek().right == temp2) {
                        temp2 = st.pop();
                    }
                }
            }
        }
    }

    public void preorder() {
        if (this.root == null) {
            return;
        }
        Stack<Node> st = new Stack<>();
        st.push(this.root);
        Node temp;
        while (!st.empty()) {
            temp = st.pop();
            if (temp.right != null) {
                st.push(temp.right);
            }
            if (temp.left != null) {
                st.push(temp.left);
            }
        }
    }




    private static class Node {
        int data;
        Node left;
        Node right;

        Node(int d) {
            data = d;
            left = null;
            right = null;
        }
    }
}